1. Field of the Invention
The present invention relates to data flow management circuitry in computer systems and, more particularly, to data pipelining for error correction/detection circuitry in computer systems using interleaved memory.
2. Description of Related Art
As is well known to those skilled in the art, a computer system consists of a number of subsystems interconnected by paths that transfer data between the subsystems. Two such subsystems are a central processing unit ("CPU") or processor and a memory and storage subsystem ("memory") which may comprise multiple memory devices. The CPU controls the operation of the computer system by executing a sequence of instructions to perform a series of operations on data. Both the instructions and the data are stored in the computer's memory as binary information, patterns of logical ones and zeros.
As is further well known to those skilled in the art, a "bus" in the computer, that is, the communications channel between the CPU and the various memory and storage devices, is inherently a bottleneck, limiting the speed at which data can be processed within the system. Virtually all instructions and all data to be processed must travel this route at least once. To maximize computer system performance, computer designers have employed different schemes to increase system processing speed including those which enhance the efficiency with which data is moved from the memory and storage devices to the CPU so that the CPU never has to wait unnecessarily for the information it needs to do its work.
Although it might seem that the most direct route to efficiently move the information might be to fill the computer with the fastest memory possible, this is impractical because even if enough such memory could be installed, the cost of such a memory would be prohibitive. Therefore, computer designers have employed a variety of devices to hold data and instructions, the choice of the repository depending upon how urgently the information might be needed by the CPU. In making the various trade-offs necessary to accomplish this, in general, fast but expensive devices are used to satisfy the CPU's immediate needs and slower but more economic devices are used to retain information for future use.
One technique used in design of personal computers to increase the speed at which the CPU can obtain access to data is that of a cache memory. This is a high speed memory device located close to the CPU in which is stored the information which the CPU is most likely to need next in its processing operations. It is statistically true that a CPU is most likely to need next the data which it most recently accessed. The next most likely is data which is immediately adjacent that which the CPU just previously accessed. For this reason, cache memory systems are configured so that the first place the CPU tries to locate the address of data which it needs for its operations is in the cache memory. If it fails to find that address in the cache, it then retrieves the data from system memory, which requires more time, and stores the new data in the cache memory for future reference. Thus, reducing the time required to retrieve data words from systems memory and store them in cache memory will enhance the overall throughput speed of a system.
Another technique of increasing the speed of a computer system is to handle the data to be processed in larger units so that more bits of data are moved through the system per unit of time. The present state of the art processors, such as the 80386 (386) and 80486 (486) microprocessors made by Intel Corporation, utilize 32 bit, so-called, double word architectures to handle data faster than the prior art processors which used 16 bit words. Similarly, storing and handling data in system memory in 64 bit units, i.e., four contiguous words of 16 bits each or two contiguous double words of 32 bits each, would also enable faster access. However, both connector pin limitations and the fact that current CPUs process data with 32 bit double words make it necessary to transmit and handle data in 32 bit units even though 64 bit wide memories can be implemented by interleaving two 32 bit memory banks. Interleaving is discussed in more detail below.
A serious limitation on the speed and reliability of computer systems is inherent in the data errors which are a fact of life for computers. Whenever data is transmitted or wherever it is stored it is vulnerable to many different forces and conditions that can physically distort the data words, changing zeros into ones and vice versa. The consequences of data errors can be devastating; a single wrong bit can change the meaning of an entire sequence of bits, perhaps throwing off a lengthy mathematical calculation or causing a computer to misinterpret a command. A number of strategies have been developed to allow computers to detect and, in some configurations, to correct errors. Error detection schemes are relatively easy and inexpensive to implement and therefore most personal computer systems include them. Error correction systems are considerably more expensive.
The most common method of detecting an error is known as parity checking. Parity checking involves counting the numbers of ones in a series of bits, and then adding a one or zero as an extra digit, known as a parity bit, to make the total number of ones come out even, for even parity systems, or odd, for odd parity systems. To confirm that the bits have not changed after each transmission or storage, the number of ones in each word are recounted, and if the result is an odd number for even parity systems, it indicates that an error has occurred. The system can then either retrieve and recreate the original data word before going on, to avoid an error, or it can simply provide a signal indicating to the user that an error has occurred.
Parity checking systems rely on an exclusive-or operation to do their counting of ones. This operation labels odd sets of ones and even sets with a 0, so coding is simply a matter of appending these results to the original data word as the parity bit. Odd sets automatically become even with the extra one, and even sets remain unchanged by the extra zero.
Parity checking works most effectively when the errors are few and far between. If there are two errors within a group of bits that share a parity bit, the number of ones will remain even and the errors will go undetected. Furthermore, parity checking cannot correct errors and is not adequate as a defense against data errors when there is a permanent defect in the memory cell or other storage element that makes retransmission ineffective as a remedy. Such situations call for more elaborate coding strategies capable of correcting the problem as well as detecting it.
Because of the inherent, two-state simplicity of binary numbers, computers can correct an error in a group of bits merely by switching a zero back to a one or vice versa. But first the computer must determine exactly which bit or bits is erroneous, and such determination requires a certain measure of ingenuity.
Various error correcting schemes are well-known to those skilled in the art including, for example, the so-called Hamming codes and Reed-Soloman codes, which each were named for their respective inventors. These techniques, which are variously designed to guard different quantities of information, combine the various data bits comprising each word in logical relationships which generate an additional set of bits known as syndrome bits which are associated with each word stored in the computer. A detailed discussion of the theory of error correction codes ("ECC") is beyond the scope of the present application. Suffice it to say that the ECC employed in the system of the present invention generates 7 syndrome bits for each 32 bit data word, producing a 39 bit word to be stored in memory. This ECC scheme is capable of single bit error correction and double bit error detection.
As discussed above, interleaving can also be used to enable the faster handling of data in a computer system. For example, the system of the present invention stores data in 64 bit blocks in the main memory, but because the processor and ECC circuitry only handles 32 bit double words, interleaving is used to handle the entry and retrieval of each pair of 32 bit double words comprising a 64 bit block (actually each 32 bit data word comprises 39 bits, since with ECC each word also includes 7 syndrome bits, so that a total 78 bit block is formed).
Needless to say, unifying ECC and interleaving to handle large virtual words in memory into a simple, efficient system is very difficult. Although a number of computer systems have been heretofore developed, these prior art systems have not efficiently used error correction circuitry in a system including interleaved memory, in which only one signal is used to latch the data and in which the system allows 64 bits of data to be read from memory at a time, rather than 32, to significantly increase the system throughput.